package day_2022_4_to_7.nowcoder;

/**
 * 删除链表中重复节点
 * @author haomin
 * @date 2022/04/18 08:38
 **/
public class DeleteDuplication_16f {
    public ListNode deleteDuplication(ListNode pHead) {
        if(pHead == null){
            return null;
        }
        // 定义一个虚拟头结点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = pHead;
        // 定义快慢指针
        ListNode pre = dummyNode;
        ListNode last = pre.next;

        while(last != null){
            // 找到重复节点
            while(last.next != null && last.val != last.next.val){
                pre = pre.next;
                last = last.next;
            }
            // 找到重复节点的末位置
            while(last.next != null && last.val == last.next.val){
                last =last.next;
            }
            // 三种结果
            // 1. last == null, prev.next == last 没有相同值的节点
            // 2. last == null, prev.next != last 最后一个节点也是重复节点，需去重
            // 3. last != null, prev.next != last 找到了其中一个一个相同值节点的末位置，需去重

            // 有重复节点，需去重
            if(pre.next != last){
                pre.next = last.next;
            }
            last = last.next;
        }
        return dummyNode.next;
    }
}